package leo.mystudy.leetcode.nodelist;

import leo.mystudy.leetcode.ListNode;

/**
 * @author leo
 * @version 1.0.0
 * @description 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：head = [1,2,2,1]
 * 输出：true
 * 示例 2：
 * <p>
 * <p>
 * 输入：head = [1,2]
 * 输出：false
 *  
 * <p>
 * 提示：
 * <p>
 * 链表中节点数目在范围[1, 105] 内
 * 0 <= Node.val <= 9
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xaw0rm/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * 1,2,1,1,2,1
 * 1.1.2.2.1.1
 * @create 2022/3/15 15:52
 */
public class IsPalindrome {

    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return true;
        }
        // 用快慢指针找转折点
        ListNode slow = head;
        ListNode fast = head;
        ListNode left = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            ListNode next = slow.next;
            // 将慢指针追加到左链表
            slow.next = left;
            left = slow;
            slow = next;
        }
        if (fast != null) {
            // 链表长度为奇数时，slow向前进一位
            slow = slow.next;
        }
        while (left != null && slow != null) {
            if (left.val != slow.val) {
                return false;
            }
            left = left.next;
            slow = slow.next;
        }
        return left == null && slow == null;
    }

    public static void main(String[] args) {
//        ListNode listNode = ListNode.build(new int[]{8, 0, 7, 1, 7, 7, 9, 7, 5, 2, 9, 1, 7, 3, 7, 0, 6, 5, 1, 7, 7, 9, 3, 8, 1, 5, 7, 7, 8, 4, 0, 9, 3, 7, 3, 4, 5, 7, 4, 8, 8, 5, 8, 9, 8, 5, 8, 8, 4, 7, 5, 4, 3, 7, 3, 9, 0, 4, 8, 7, 7, 5, 1, 8, 3, 9, 7, 7, 1, 5, 6, 0, 7, 3, 7, 1, 9, 2, 5, 7, 9, 7, 7, 1, 7, 0, 8});
        ListNode listNode = ListNode.build(new int[]{1, 3, 3, 1});
        System.out.println(new IsPalindrome().isPalindrome(listNode));
    }
}
